package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 437. 路径总和 III
 * 深度优先搜索
 * 自顶向下
 *
 * @author fy
 * @date 2022/4/25 16:41
 */
public class Solution437 {

    private int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        dfs(root, targetSum, false);
        return count;
    }

    public void dfs(TreeNode node, int targetSum, boolean hasStart) {
        if (node == null) {
            return;
        }
        // 找到了一条为0的路径, 这里不能return, 因为后续相加还是有可能为0
        if (targetSum == node.val) {
            count++;
        }
        if (!hasStart) {
            dfs(node.left, targetSum, false);
            dfs(node.right, targetSum, false);
        }
        dfs(node.left, targetSum - node.val, true);
        dfs(node.right, targetSum - node.val, true);
    }

}
